package my.jwds.p160;

import my.jwds.p21.ListNode;

import java.util.HashSet;
import java.util.Set;

public class GetIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set set = new HashSet();
        while(headA!= null){
            if (set.contains(headA)){
                return headA;
            }
            set.add(headA);
            headA = headA.next;
        }
        while(headB!= null){
            if (set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }


    public ListNode getIntersectionNode_twoPointer(ListNode headA, ListNode headB){
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2){
            p1 = p1 == null?headB:p1.next;
            p2 = p2 == null?headA:p2.next;
        }
        return p1;


    }
}
